package q84_largestRectangleArea;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_2 {
    public static void main(String[] args) {
        Solution_2 soluion = new Solution_2();
    }

    /**
     * 从解法一的思路上来看，我们解题的核心在于寻找柱子两侧的第一个小于它的柱子，那么是否存在只需要遍历一次或两次就能够找到柱子两侧的办法？
     * 这里同样使用了单调栈的方法，首先从左往右遍历，找到每一个柱子右边第一个小于它的柱子
     */
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }

        int res = 0;

        // 需要两个数组来分别记录柱子左右两侧第一个小于它的柱子位置
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];

        Deque<Integer> stack = new LinkedList<>();
        // 先来找每个柱子左边第一个小于它的柱子，用left数组来记录第一个小于它柱子的位置
        for (int i = 0; i < heights.length ; i++) {
            // 如果栈顶的那个柱子比当前的柱子大，意味着还要继续找，一直找到第一个小于它的柱子
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            // pop()的过程结束后，那么栈顶的元素就是第一个小于它的柱子的位置了，如果没有，意味着一直到最左边都没有小于它的柱子。
            left[i] = (stack.isEmpty() ? -1 : stack.peek());
            // 每一个i都要被压入栈中
            stack.add(i);
        }
        stack.clear();

        // 然后找每个柱子右边第一个小于它的柱子
        for (int j = heights.length - 1; j >= 0 ; j--) {
            // 如果栈顶的那个柱子比当前的柱子大，意味着还要继续找
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[j]) {
                stack.pop();
            }
            // pop()的过程结束后，那么栈顶的元素就是第一个小于它的柱子的位置了，如果没有，意味着一直到最左边都没有小于它的柱子。
            right[j] = (stack.isEmpty() ? heights.length : stack.peek());
            // 每一个i都要被压入栈中
            stack.add(j);
        }

        for (int i = 0; i < heights.length; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }

        return res;
    }
}
